package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 12/10/20 2:37 PM
 *
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 */
public class _5_最长回文子串_02 {

    public String longestPalindrome(String s) {

        if (s == null) {

            return null;
        }

        if (s.length() == 1) {

            return s;
        }

        char[] sChar = s.toCharArray();

        int index=0,len = 1;

        for (int i = 1; i < sChar.length - 1; i++) {

            /**
             * 奇数中心扩展
             */
            int oddLen = findLength(sChar, i - 1, i + 1);

            /**
             * 偶数中心扩展
             */
            int evenLen = findLength(sChar,i,i+1);

            int maxLen = Math.max(oddLen, evenLen);
            if (maxLen > len) {

                len = maxLen;
                index = i - ((maxLen -1) >> 1);
            }
        }

        // 处理第一个间隙
        if (len < 2 && sChar[0] == sChar[1]) {

            len = 2;
            index = 0;
        }

        return s.substring(index,index+len);
    }

    private int findLength(char[] sChar, int left, int right) {

        while (left >= 0 && right< sChar.length && sChar[left] == sChar[right]) {

            left--;
            right++;
        }

        /**
         * 这个时候 right left 不相等，要获取的是 (left,right) 之间的长度
         * 而 [left,right] 的长度为: right - left + 1 ,不算首尾，即 right - left + 1 - 2
         * 即为 right - left - 1
         */
        return right - left - 1;
    }
}
